//赋值随机指针的链表
struct Node* copyRandomList(struct Node* head) {

	if (!head)
		return NULL;
	struct Node* cur = head;
	struct Node* next = NULL;
	struct Node* new_head = NULL;
//插入新指针
	while (cur) {
		struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
		next = cur->next;
		cur->next = new_node;
		new_node->next = next;
		new_node->val = cur->val;
		cur = next;
	}
	new_head = head->next;//第一个插入的节点
//随机指针赋值
	cur = head;
	while (cur) {
		next = cur->next;
		if (!cur->random)
			next->random = cur->random;
		else
			next->random = cur->random->next;
		cur = next->next;
	}
//链表恢复和组合
	cur = head;
	while (cur->next) {
		next = cur->next;
		cur->next = next->next;
		cur = next;
	}
	return new_head;
}